package com.zwj.interview.DFS;



/**
 * 在一棵二叉树中所有节点都在0～9的范围之内，从根节点到叶节点的路径表示一个数字。
 * 求二叉树中所有路径表示的数字之和。例如，图8.4的二叉树有3条从根节点到叶节点的路径，
 * 它们分别表示数字395、391和302，这3个数字之和是1088
 * <p>
 * 3
 * 9     0
 * 5   1      2
 * <p>
 * 结果:395+391+302=1088
 */
public class 从根节点到叶子节点的路径和 {

    /**
     * 首先考虑如何计算路径表示的数字。顺着指向子节点的指针路径向下遍历二叉树，每到达一个节点，
     * 相当于在路径表示的数字末尾添加一位数字。例如，在最开始到达根节点时，它表示数字3。然后到达节点9，
     * 此时路径表示数字39（3×10+9=39）。然后向下到达节点5，此时路径表示数字395（39×10+5=395）
     *
     * @param root
     * @return 这就是说，每当遍历到一个节点时都计算从根节点到当前节点的路径表示的数字。
     * 如果这个节点还有子节点，就把这个值传下去继续遍历它的子节点。先计算到当前节点为止的路径表示的数字，
     * 再计算到它的子节点的路径表示的数字，这实质上就是典型的二叉树前序遍历
     */
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }


    //辅助函数，深度优先
    private int dfs(TreeNode root, int path) {
        if (root == null) {
            return 0;
        }
        path = root.val+path*10;
        //没有左右子节点了，返回path即可
        if (root.left == null && root.right == null) {
            return path;
        }
        //递归返回分别以左右子节点为根节点的
        return dfs(root.left, path) + dfs(root.right, path);
    }


}
